# Python 2.6.4
# Project Euler, Problem 107
# Copyright 2010 Talha Zaman

def connected(matrix):
    flags = [False]*len(matrix)
    visit(0, flags, matrix)
    return all(flags)

def visit(node, flags, matrix):
    if flags[node]==True: return
    flags[node] = True
    for i in range(len(matrix)):
        if matrix[node][i]!="-":
            visit(i, flags, matrix)

def revdel(matrix):
    weights = []
    for i in range(len(matrix)):
        for j in range(i+1, len(matrix)):
            if matrix[i][j]!="-": weights.append(int(matrix[i][j]))
    weights.sort()
    while len(weights):
        top = str(weights.pop())
        for i in range(len(matrix)):
            for j in range(i+1, len(matrix)):
                if matrix[i][j]!="-" and matrix[i][j]==top:
                    matrix[i][j] = matrix[j][i] = "-"
                    if not connected(matrix):
                        matrix[i][j] = matrix[j][i] = top

def weight(matrix):
    return sum(sum(int(matrix[i][j]) for j in range(len(matrix)) \
                   if matrix[i][j]!="-") for i in range(len(matrix)))/2

net = [x.strip().split(',') for x in open("network.txt").readlines()]
tot = weight(net)
revdel(net)
spn = weight(net)
print tot, "-", spn, "=", tot-spn
